#define  _CRT_SECURE_NO_WARNINGS
class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size(), ret = 0;
        vector<vector<bool>> dp(n, vector<bool>(n));
        for (int i = 0; i < n; i++)
            for (int j = 0; j <= i; j++)
                if (s[i] == s[j])
                    ret += dp[i][j] =
                    i == j || i == j + 1 ? true : dp[i - 1][j + 1];
        return ret;
    }
};
